package algorithm_demo.demo03;

/**
 * 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
 * 对于以X为头的树，有以下三种可能性
 * 与X无关：
 * 1）左树的最大距离
 * 2）右树的最大距离
 * 与X有关：
 * 3）左树最远（高度） + 右树最远（高度）+ 1
 *
 * @author Api
 * @date 2023/2/12 9:44
 */
public class Code03_MaxDistance {
    public static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    public static class Info{
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height){
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }

    public static int maxDistance(Node x){
        return process(x).maxDistance;
    }


    public static Info process(Node x){
        if (x == null){
            return new Info(0,0);
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height)+1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.maxDistance+ rightInfo.maxDistance+1;
        int maxDistance = Math.max(p3, Math.max(p1, p2));
        return new Info(maxDistance, height);
    }
}
